home *** CD-ROM | disk | FTP | other *** search
- Path: ix.netcom.com!news
- From: Bradd W. Szonye <bradds@ix.netcom.com>
- Newsgroups: comp.lang.c++
- Subject: RE: Fastest Sorting Algorithm?
- Date: 19 Apr 1996 09:45:44 GMT
- Organization: Netcom
- Message-ID: <01bb2dd5.45612920$c6c2b7c7@Zany.localhost>
- References: <Dou55w.7MB@novice.uwaterloo.ca> <DpAxtI.3w9@undergrad.math.uwaterloo.ca> <4k15rt$nbb@news.microsoft.com>
- NNTP-Posting-Host: det-mi6-06.ix.netcom.com
- X-NETCOM-Date: Fri Apr 19 4:45:44 AM CDT 1996
- X-Newsreader: Microsoft Internet News
-
-
- On Thursday, April 04, 1996, Dann Corbit wrote...
- > In article <DpAxtI.3w9@undergrad.math.uwaterloo.ca>,
- sckettle@undergrad.math.uwaterloo.ca says...
- > >
- > >In article <Dou55w.7MB@novice.uwaterloo.ca>,
- > >Gerald Wang <GTWANG@HELIX.Watstar.UWaterloo.CA> wrote:
- > >>A classmate was recently asked during a job interview what is the
- fastest
- > >>method to sort an array of numbers. He replied "Use a quicksort." They
-
- > >>asked "And how would you make it faster still?" He couldn't come up
- with
- > >>much...end of interview.
- > >>
- > >>I know it's a vague question... Any ideas on what they were asking? Or
-
- > >>what the right answer is?
- > >>
- > >>Gerald
- > >>
- >
- >>------------------------------------------------------------------------
- -
- > >>Gerald Wang
- > >>http://www.csclub.uwaterloo.ca/~gtwang
- > >>
- > >>
- > >
- > >Well you could use a type of bucket sorting algorithm which is faster
- than
- > >quicksort when sorting integers. How to make it faster I don't know -
- you
- > >don't really make algortithms faster you make code implementations of
- > >algorithms faster. Mybe they meant tweaking stratigies for quicksort
- like how
- > >to choose a pivot element. Who knows.
- > Bucket sort, counting sort and radix sort are all faster if there are a
- > large number of elements.
- >
- > Their question about how to make it faster still was probably to see how
- > he tackles problems. They may have wanted something like:
- > 1. Research avalable sorting algorithms
- > 2. Select best algorithm for problem space
- > 3. Profile the chosen implementation to find bottlenecks
- > 4. Optimize the small fraction of code that is the greatest bottleneck.
- >
- > Alternatives:
- > 1. Buy a sorting package
- > 2. Use a database to do the sorting
- >
- > --
- > The opinions expressed in this message are my own personal views
- > and do not reflect the official views of Microsoft Corporation.
- > In fact, I'm just a subcontractor, not an employee, so pull in your
- claws.
- >
- >
-
- The fastest sort depends on what you're trying to do.
-
- For large, arbitrary, badly-distributed, memory-based data, Quicksort is
- great.
- For disk-based data, Mergesort is great.
- For well-distributed binary data, radix sort is great.
- For small data sets, insertion sort is great.
-
-
-